export class FDT{
    N:number;//节点数
    root:number;//根节点标号
    cnt:number;
    fa:number[];
    children:Array<number>[];
    first:number[];
    second:number[];

    constructor(N:number,root:number){
        this.N=N;
        this.root=root;
        this.cnt=0;
        this.fa=new Array<number>(N+10);
        this.first=new Array<number>(N+10);
        this.second=new Array<number>(N+10);
        this.children=new Array<Array<number>>(N+10);
        for(let i=0;i<=N+9;i++){
            this.children[i]=new Array<number>;
        }
    }
    public addEdge(u:number,v:number){
        this.fa[v]=u;
        this.children[u].push(v);
    }
    private dfs(x:number){
        // console.log(x);
        this.cnt++;this.first[x]=this.cnt;
        for(let i of this.children[x]){
            this.dfs(i);
        }
        this.second[x]=this.cnt;
    }
    public init(){
        this.dfs(this.root);
    }
    public isGrand(a:number,b:number):boolean{
        return this.first[a]<this.first[b] && this.first[b]<this.second[a];
    }
}